#include "BinaryTree.h"

BTreeNode* CreateBinaryTree() {
/*       A
       /   \
      B     C
     / \   / \ 
    D   E F   G 
         \     
          H    */
    BTreeNode* A = CreateBTreeNode('A');
    BTreeNode* B = CreateBTreeNode('B');
    BTreeNode* C = CreateBTreeNode('C');
    BTreeNode* D = CreateBTreeNode('D');
    BTreeNode* E = CreateBTreeNode('E');
    BTreeNode* F = CreateBTreeNode('F');
    BTreeNode* G = CreateBTreeNode('G');
    BTreeNode* H = CreateBTreeNode('H');
    A->_left = B;    A->_right = C;
    B->_left = D;    B->_right = E;
    E->_right = H;
    C->_left = F;    C->_right = G;
    return A;
}

BTreeNode* CreateBTreeNode(BTreeDataType value) {
    BTreeNode* node = (BTreeNode*)malloc(sizeof(BTreeNode));
    node->_left = NULL;     node->_right = NULL;
    node->_data = value;    return node;
}

void PrevOrder(BTreeNode* root) { // 先序遍历
    if(!root)  return;
    printf("%c ", root->_data);
    PrevOrder(root->_left);
    PrevOrder(root->_right);
}

void InOrder(BTreeNode* root) {  // 中序遍历
    if(!root)  return;
    InOrder(root->_left);
    printf("%c ", root->_data);
    InOrder(root->_right);
}

void PostOrder(BTreeNode* root) { // 后序遍历
    if(!root)  return;
    PostOrder(root->_left);
    PostOrder(root->_right);
    printf("%c ", root->_data);
}

int BTreeSize(BTreeNode* root) { // 二叉树的结点数
    if(!root)  return 0;
    return BTreeSize(root->_left) + BTreeSize(root->_right) + 1;
}

int BTreeLeafSize(BTreeNode* root) { // 二叉树的叶子结点数
    if(!root)  { return 0; }
    else if(!(root->_left) && !(root->_right)) { return 1; }
    else { return BTreeLeafSize(root->_left) + BTreeLeafSize(root->_right); }
}

int BTreeNodeHight(BTreeNode* root) { // 结点的高度
    if(!root) { return -1; }
    else if(!(root->_left) && !(root->_right)) { return 0; }
    else { 
        int leftHight = BTreeNodeHight(root->_left);
        int rightHight = BTreeNodeHight(root->_right);
        return 1 + ((leftHight >= rightHight) ? leftHight : rightHight);
    }
}

int BTreeLevelKSize(BTreeNode* root, int k) { // 二叉树第k层结点个数
    if(!root)  return 0;     if(k == 1) return 1;
    return (BTreeLevelKSize(root->_left, k - 1) + BTreeLevelKSize(root->_right, k - 1));
}

BTreeNode* BinaryTreeFind(BTreeNode* root, BTreeDataType value) {
    if(!root) return NULL;    // 二叉树查找值为value的结点
    if(root->_data == value)  return root;
    BTreeNode* res = BinaryTreeFind(root->_left, value);
    if(!res) { res = BinaryTreeFind(root->_right, value); }
    return res;
}

void BTreeDestory(BTreeNode* root) { // 销毁二叉树
    if(!root)  return;
    BTreeDestory(root->_left);
    BTreeDestory(root->_right);
    free(root);
}

void BTreeLevelOrdef(BTreeNode* root) { // 层序遍历
    if(!root)  return;
    Queue queue;    QueueInit(&queue);
    QueuePush(&queue, root);
    while(!QueueEmpty(&queue)){
        BTreeNode* front = QueueFront(&queue);
        QueuePop(&queue);
        printf("%c ", front->_data);
        if(front->_left) QueuePush(&queue, front->_left);
        if(front->_right) QueuePush(&queue, front->_right);
    }   QueueDestory(&queue);
}

bool BinaryTreeComplete(BTreeNode* root) { // 判断二叉树是否是完全二叉树
    // 基于层序遍历
    if(!root)  return true;
    Queue queue;    QueueInit(&queue);
    QueuePush(&queue, root);
    while(!QueueEmpty(&queue)) {
        BTreeNode* front = QueueFront(&queue);
        QueuePop(&queue);
        if(front == NULL) break;
        QueuePush(&queue, front->_left);
        QueuePush(&queue, front->_right);
    }
    while(!QueueEmpty(&queue)) {
        BTreeNode* front = QueueFront(&queue);
        if(front != NULL) { QueueDestory(&queue);  return false; }
        QueuePop(&queue);
    }   QueueDestory(&queue);  return true;
}